πŸ‘©β€πŸ’» 2437. μ €μšΈ

@Seongukbaek Posted March 04, 2022 Β· Updated March 04, 2022 Β· 3 min read

문제

ν•˜λ‚˜μ˜ μ–‘νŒ” μ €μšΈμ„ μ΄μš©ν•˜μ—¬ 물건의 무게λ₯Ό μΈ‘μ •ν•˜λ €κ³  ν•œλ‹€. 이 μ €μšΈμ˜ μ–‘ νŒ”μ˜ λμ—λŠ” λ¬Όκ±΄μ΄λ‚˜ μΆ”λ₯Ό μ˜¬λ €λ†“λŠ” μ ‘μ‹œκ°€ 달렀 있고, μ–‘νŒ”μ˜ κΈΈμ΄λŠ” κ°™λ‹€. λ˜ν•œ, μ €μšΈμ˜ ν•œμͺ½μ—λŠ” μ €μšΈμΆ”λ“€λ§Œ 놓을 수 있고, λ‹€λ₯Έ μͺ½μ—λŠ” 무게λ₯Ό μΈ‘μ •ν•˜λ €λŠ” 물건만 μ˜¬λ €λ†“μ„ 수 μžˆλ‹€.

λ¬΄κ²Œκ°€ μ–‘μ˜ μ •μˆ˜μΈ N개의 μ €μšΈμΆ”κ°€ μ£Όμ–΄μ§ˆ λ•Œ, 이 좔듀을 μ‚¬μš©ν•˜μ—¬ μΈ‘μ •ν•  수 μ—†λŠ” μ–‘μ˜ μ •μˆ˜ 무게 쀑 μ΅œμ†Ÿκ°’μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

예λ₯Ό λ“€μ–΄, λ¬΄κ²Œκ°€ 각각 3, 1, 6, 2, 7, 30, 1인 7개의 μ €μšΈμΆ”κ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, 이 μΆ”λ“€λ‘œ μΈ‘μ •ν•  수 μ—†λŠ” μ–‘μ˜ μ •μˆ˜ 무게 쀑 μ΅œμ†Ÿκ°’μ€ 21이닀.

μž…λ ₯

  • 첫 μ§Έ μ€„μ—λŠ” μ €μšΈμΆ”μ˜ 개수λ₯Ό λ‚˜νƒ€λ‚΄λŠ” μ–‘μ˜ μ •μˆ˜ N이 μ£Όμ–΄μ§„λ‹€. N은 1 이상 1,000 μ΄ν•˜μ΄λ‹€. λ‘˜μ§Έ μ€„μ—λŠ” μ €μšΈμΆ”μ˜ 무게λ₯Ό λ‚˜νƒ€λ‚΄λŠ” N개의 μ–‘μ˜ μ •μˆ˜κ°€ λΉˆμΉΈμ„ 사이에 두고 μ£Όμ–΄μ§„λ‹€. 각 μΆ”μ˜ λ¬΄κ²ŒλŠ” 1이상 1,000,000 μ΄ν•˜μ΄λ‹€.

좜λ ₯

  • 첫째 쀄에 μ£Όμ–΄μ§„ μΆ”λ“€λ‘œ μΈ‘μ •ν•  수 μ—†λŠ” μ–‘μ˜ μ •μˆ˜ 무게 쀑 μ΅œμ†Ÿκ°’μ„ 좜λ ₯ν•œλ‹€.

πŸ“ Logic

Arrays.sort(nums);
  • μž…λ ₯된 μ €μšΈμΆ”λ“€μ„ μ •λ ¬ν•œλ‹€.
for (int i = 0; i < N; i++) { if (sum + 1 < nums[i]) break; sum += nums[i]; }
  • μ£Όμ–΄μ§„ μΆ”λ“€λ‘œ μΈ‘μ • κ°€λŠ₯ν•œ 무게λ₯Ό μ°ΎλŠ” 반볡문

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] nums = Arrays.stream( br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); int sum = 0; Arrays.sort(nums); for (int i = 0; i < N; i++) { if (sum + 1 < nums[i]) break; sum += nums[i]; } System.out.println(sum + 1); br.close(); } }

✏️ Review

  • c++둜 ν’€μ—ˆμ„ λ‹Ήμ‹œ μ™œ μ΄λ ‡κ²Œ 풀이가 κ°„λ‹¨ν• κΉŒλ₯Ό κ³ μ‹¬ν–ˆλ˜ 것 κ°™μ•„ Java둜 λ‹€μ‹œ ν’€μ–΄λ³΄μ•˜λ‹€.
  • μΈ‘μ •ν•  λ¬΄κ²ŒλŠ” μ£Όμ–΄μ§„ μ €μšΈμΆ”λ‘œ 츑정이 κ°€λŠ₯ν•œ 경우, μ£Όμ–΄μ§„ μ €μšΈμΆ”μ˜ 무게λ₯Ό λ”ν•˜κ³ , 거기에 +1 ν•œ λ¬΄κ²Œμ™€ λ‹€μŒ μ €μšΈμΆ”μ˜ 무게λ₯Ό λΉ„κ΅ν•œλ‹€.
  • λ‹€μ‹œ 봐도 λ­”κ°€ λͺ…μΎŒν•˜κ²Œ μ΄ν•΄λŠ” κ°€μ§€ μ•Šμ•„ λ‹€μŒμ— λ‹€μ‹œ ν’€λΌκ³ ν•˜λ©΄ 또 헀맬 κ±° κ°™λ‹€..γ…‹γ…‹

πŸ“• 좜처

https://www.acmicpc.net/problem/2437

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€